# -*- coding: utf-8 -*-
"""
structure analysis based on lyric only by finding repetition

the basic problem : what is the structure of a lyric, from a larger scale view
or smaller view the result may be different
"""

from Lyric import Lyric
from common_func import _sen_similar,print_seg,_insertlist
from suffix_tree_substring import get_frequent_common
import re,copy

import logging
logging.basicConfig(format='%(levelname)s:%(message)s', level=logging.DEBUG)

sadebug = False
sa1debug = False

def analysis(lyric):
    linelist = lyric.getlinelist()
    slist = [[0,len(linelist)-1]]
    _ana1(linelist,slist)
    if sadebug:
        logging.info('ana1')
        #printseg(linelist,slist)
    return slist

def _ana2(linelist,slist):
    # TODO delete this part of code 
    bitnum = 2
    # create the suffix structure for comparison
    name_list = range(len(linelist))
    for i in range(1,len(linelist)):
        for j in range(i):
            if linelist[i]['content'] == linelist[j]['content']:
                name_list[i] = name_list[j]
                break

    name_str = ""
    index_name_list = []
    for i,n in enumerate(name_list):
        name_str += "%02d"%(n)
        index_name_list.append( (i,n) )
        print n,linelist[i]['content'].decode('utf-8')#,index_name_list_list
    index_name_list_list = [ index_name_list ]
    
    split_list = [(0,len(linelist),name_str)]
    seg_list = []
    iter_num = 0
    while True:
        tmp_list = [ i[2] for i in split_list ]
        sub_str = get_frequent_common( tmp_list )
        if len(sub_str) < 3*bitnum:
            break
        n_split_list = []
        for b,e,name_str in split_list:
            if name_str.count(sub_str) == 0:
                n_split_list.append( (b,e,name_str) )
            else:
                # TODO ...
                # remove the subsequence here and create new split list
                # store into the structure
                for m in re.finditer(sub_str,name_str):
                    seg_list.append( (b+m.start(),b+m.end()) )


def _ana1(linelist,slist):
    """
    use the suffix array for the longest repeated substring finding
    """
    # TODO this function is too long

    bitnum = 2

    # create the suffix structure for comparison
    name_list = range(len(linelist))
    for i in range(1,len(linelist)):
        for j in range(i):
            if linelist[i]['content'] == linelist[j]['content']:
                name_list[i] = name_list[j]
                break

    # TODO change name? 
    # index_name_list seem to be used for the sub string record
    name_str = ""
    index_name_list = []
    for i,n in enumerate(name_list):
        name_str += "%02d"%(n) # TODO change with bitnum here
        index_name_list.append( (i,n) )
        print n,linelist[i]['content'].decode('utf-8')#,index_name_list_list
    index_name_list_list = [ index_name_list ]

    seg_list = []
    iter_num = 0
    while True:

        # TODO this is for debug
        iter_num += 1
        print "### begin of iter %d ###"%(iter_num)
        # print index_name_list_list info
        print 'index name list list'
        for index_name_list in index_name_list_list:
            begin_index = index_name_list[0][0]
            end_index = index_name_list[-1][0]+1  #end_index is the number after
            print name_str[begin_index*bitnum:end_index*bitnum]

        
        # build the suffix array for each of the index_name_list
        suffix_array = []
        for index_name_list in index_name_list_list:
            begin_index = index_name_list[0][0]
            end_index = index_name_list[-1][0]+1  #end_index is the number after

            # for each substring structure, create the suffix array for it
            for i in range(begin_index,end_index):
                suffix_array.append(
                        (i, end_index, name_str[i*bitnum:end_index*bitnum]) )
        suffix_array.sort( lambda x,y:cmp(x[2],y[2]) )


        # get the largest common substring
        #print len(suffix_array)
        #for sa in suffix_array:
        #    print sa


        # after get the longest common string, 
        # rebuild the index_name_list_list, store the new structure
        max_len = -1
        sub_str = ""
        for i in range( len(suffix_array)-1 ):
            # compare with i+1
            start1 = suffix_array[i][0]
            start2 = suffix_array[i+1][0]
            com_len = get_common_length( 
                    suffix_array[i][2], suffix_array[i+1][2] ,
                    start1*2 , start2*2)

            # TODO this is the debug part
            if com_len > max_len:
                max_len = com_len
                sub_str = suffix_array[i][2][:com_len]
                print max_len,sub_str,suffix_array[i][2],suffix_array[i+1][2],\
                        start1*2,start2*2


        print 'best sub str',sub_str
        # not found the best match, then break
        if len(sub_str) < 3*bitnum:
            break

        # find all suffix_array in current index_name_list_list for re-build
        # store the new structure
        new_index_name_list = []
        for index_name_list in index_name_list_list:
            begin_index = index_name_list[0][0]
            end_index = index_name_list[-1][0]+1
            tmp_name_str = name_str[begin_index*bitnum:end_index*bitnum]

            print tmp_name_str,sub_str
            if tmp_name_str.count(sub_str) == 0:
                new_index_name_list.append( copy.deepcopy(index_name_list) )
                continue
            else:

                m_list = []
                for m in re.finditer( sub_str,tmp_name_str ):
                    m_list.append(m)

                # TODO if find multiple match sequence
                # simply get the beginning and ending of such sequences
                # write another function that process this
                if len(m_list) != 1:
                    raise Exception( 'm list len %d not equal to 1'%(len(m_list)) )
                # TODO the seg_list

                m = m_list[0]   # check here
                if m.start() % bitnum != 0 or m.end() % bitnum != 0:
                    #print tmp_name_str[m.start():m.end()]
                    raise Exception(
                    ' should be multiplier of 2 %d,%d'%(m.start(),m.end()))
                start_index = m.start() / bitnum 
                end_index = m.end() / bitnum - 1

                print tmp_name_str,m.start(),m.end(),\
                        tmp_name_str[m.start():m.end()],len(index_name_list)
                
                # store this
                seg_list.append(
                        (index_name_list[m.start()/bitnum][0],
                            index_name_list[m.end()/bitnum - 1][0]) ) 
                        
                print 'add seg' , seg_list[-1]

                # update the index_name_list
                if m.start() == 0 and m.end() == len(tmp_name_str):
                    continue
                elif m.start() == 0:
                    new_index_name_list.append( index_name_list[m.end()/bitnum:] )
                elif m.end() == len(tmp_name_str):
                    new_index_name_list.append(
                            index_name_list[:m.start()/bitnum] )
                else:
                    new_index_name_list.append(
                            index_name_list[:m.start()/bitnum] )
                    new_index_name_list.append( index_name_list[m.end()/bitnum:] )


        # re-assign the index_name_list_list
        index_name_list_list = new_index_name_list
        seg_list.sort(lambda x,y:cmp(x[0],y[0]))
        new_seg_list = []
        for i in range(len(seg_list)-1):
            new_seg_list.append(seg_list[i])
            if seg_list[i][1] + 1 != seg_list[i+1][0]:
                new_seg_list.append( (seg_list[i][1]+1,seg_list[i+1][0]-1) )

    print new_seg_list
    for i,seg in enumerate(new_seg_list):
        print 'seg',i,seg[0],seg[1]
        for j in range(seg[0],seg[1]+1):
            print linelist[j]['content'].decode('utf-8')

    
            # repeat:
            # 1 get the longest repeated pattern
            # 2 remove the pattern, rebuild the suffix tree, go on to find the next longest pattern

        #return 

    while True:
        orglen = len(slist)
        for seg in slist:
            #check the segment and insert into the seg
            for i in range(seg[0],seg[1]+1):
                for j in range(i+1,seg[1]+1):
                    if _senSimilar(linelist[i]['content'],linelist[j]['content']) > similarthres:
                        _insertlist(slist,j)

        if len(slist) == orglen:
            #no change
            break
        #print slist

if __name__ == "__main__":
    #c = get_common_length("1819200910111200010203181920091011120910111209101112","181920091011120910111209101112",36,58)
    #a = "1819200910111200010203181920091011120910111209101112"
    #print c,a[:c]
    #print get_frequent_common(["0001020304050607080910111213141516171819200910111200010203181920091011120910111209101112"],2)
    #exit()
    
    l = Lyric()
    #fname = "harrybobo.lrc"
    #fname = "wangfei.txt"
    fname = "she-toodetail.lrc"
    l.loadfile(fname)
    linelist = l.getlinelist()

    for i,line in enumerate(linelist):
        #print i,str(line['time'])+":"+line['content'].decode('utf-8')
        a = 1

    segs = analysis(l)
    #printseg(linelist,segs)

